package de.pass.ch.junit;

import static org.junit.Assert.*;

import java.util.Arrays;
import java.util.Random;

import org.junit.Test;

import de.pass.ch.datastr.BinaryHeapNodeOrder;
import de.pass.ch.datastr.PQueueNodeElimination;

public class TestBinaryHeapNodeOrder {

	private static final Random RANDOM = new Random();
	private static final double DELTA = 1e-15;

	@Test
	public void testBinaryHeapNodeOrder() {

		System.gc();

		int size = 100000;

		BinaryHeapNodeOrder heap = new BinaryHeapNodeOrder(size);

		double[] min = new double[size];
		// double[] min = { 6476.064072146842, -6243.444105067631,
		// 5583.851470373641, -4813.318237239866, 4738.357432511383,
		// 7563.03368955565, 7242.351219778284, 2894.057626700527,
		// 6005.290107864622, -2464.22518622307 };

		double minEl = Double.MAX_VALUE;
		int index = 0;

		// String out = "input:  ";

		for (int i = 0; i < min.length; i++) {
			double key = (RANDOM.nextDouble() + 1)
					* (RANDOM.nextInt(10000) - 5000);
			min[i] = key;
			heap.insert(min[i], new PQueueNodeElimination());

			if (key < minEl) {

				minEl = key;
				index = i;

			}

			// out += i == 0 ? "" + key : ", " + key;

		}

		// if (min.length <= 1000)
		// System.out.println(out);

		assertTrue(heap.checkHeapProperty());

		assertEquals(min.length, heap.size());

		System.out.println("index " + index + " aktualisiert von " + min[index]
				+ " zu " + (min[index] + 5000));

		min[index] = min[index] + 5000;
		heap.updateKey(index, min[index]);

		assertTrue(heap.checkHeapProperty());

		Arrays.sort(min);

		// out = "output: ";

		for (int i = 0; i < min.length; i++) {

			double heapMin = heap.min();

			// out += i == 0 ? "" + heapMin : ", " + heapMin;

			assertEquals(min[i], heapMin, DELTA);
			heap.deleteMin();

			// assertTrue(heap.checkHeapProperty());

		}

		// if (min.length <= 1000)
		// System.out.println(out);

	}

}
